package 优先级队列_堆;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/top-k-frequent-words/description/
 * 1、优先级队列的PriorityQueue在Queue下面
 * 2、Collections.reverse(list);对列表进行反转，反转
 */
public class 前K个高频单词 {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String , Integer> map = new HashMap<>();
        for (String word : words
             ) {
            map.put(word , map.getOrDefault(word , 1) + 1);
        }
        Queue<String> deque = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if (map.get(o1) == map.get(o2)){
                    return o2.compareTo(o1);
                }else {
                   return map.get(o1) - map.get(o2);
                }
            }
        });
        for (String word : map.keySet()
             ) {
            deque.offer(word);
            if (deque.size() > k){
                deque.poll();
            }
        }
        List<String> list = new ArrayList<>();
        while (!deque.isEmpty()){
            list.add(deque.poll());
        }
        Collections.reverse(list);//对列表进行反转，反转
        return list;
    }
}
